// ml:run = $bin < A-large.in > a-large.out
#include <iostream>

using ll = long long;

int const maxn = 200000;
ll phi[maxn];
bool not_prime[maxn];
ll a, n, p;

void init_phi()
{
    for (int i = 1; i < maxn; i++) phi[i] = i;
    for (int i = 2; i < maxn; i++) {
        if (not_prime[i]) continue;
        phi[i] = i - 1;
        for (int j = 2 * i; j < maxn; j += i) {
            not_prime[j] = true;
            phi[j] /= i;
            phi[j] *= (i - 1);
        }
    }
}

ll fact(ll n, ll p)
{
    ll ans = 1;
    for (int i = 1; i <= n; i++)
        ans = (ans * i) % p;
    return ans;
}

ll quick(ll a, ll b, ll p)
{
    if (b == 0) return 1 % p;
    auto ans = quick(a, b/2, p);
    ans = (ans * ans) % p;
    if (b & 1) ans = (ans * a) % p;
    return ans;
}

ll calc(ll a, ll n, ll p)
{
    ll b = fact(n, phi[p]) + phi[p];
    return quick(a, b, p);
}

int main()
{
    std::ios::sync_with_stdio(false);

    init_phi();
    int T; std::cin >> T;
    for (int ti = 1; ti <= T; ti++) {
        std::cout << "Case #" << ti << ": ";
        std::cin >> a >> n >> p;
        std::cout << calc(a, n, p) << "\n";
    }
}

